/*
 * @lc app=leetcode.cn id=778 lang=javascript
 *
 * [778] 水位上升的泳池中游泳
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
  const size = grid.length;
  const edges = [];
  // 建图
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      const idx = i * size + j;
      if (i > 0) {
        edges.push([idx, idx - size, Math.max(grid[i][j], grid[i - 1][j])]);
      }
      if (j > 0) {
        edges.push([idx, idx - 1, Math.max(grid[i][j], grid[i][j - 1])]);
      }
    }
  }
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(size * size);
  let result = 0;
  for (const edge of edges) {
    const [x, y, v] = [edge[0], edge[1], edge[2]];
    uf.union(x, y);
    if (uf.connected(0, size * size - 1)) {
      // 连通后的最近一个边就是最大的边
      result = v;
      break;
    }
  }
  return result;
};

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    let ux = this.find(x);
    let uy = this.find(y);
    if (ux === uy) {
      return false;
    }
    if (this.size[ux] > this.size[uy]) {
      [ux, uy] = [uy, ux];
    }
    this.parent[ux] = uy;
    this.size[uy] += this.size[ux];
    this.count--;
    return true;
  }
  connected(x, y) {
    let ux = this.find(x);
    let uy = this.find(y);
    return this.parent[ux] === this.parent[uy];
  }
}
// @lc code=end
